//
// Created by 123 on 2024/3/5.
//括号匹配

#include <iostream>

using namespace std;

typedef struct LinkNode {
    char data;
    LinkNode *next;

} LinkNode, *LinkStack;

//初始化
bool initStack(LinkStack &l);

//判空栈
bool isEmpty(LinkStack l);

//进栈
bool push(LinkStack &l, char e);

//出栈
bool pop(LinkStack &l, char &e);

//读取栈顶元素
bool getTop(LinkStack &l, char &e);

void show(LinkStack l);


//匹配括号
bool bracketMatch(char c[], int length);

int main() {
    int length=4;
    char a[10]={'(','{',']',')','}'};
    if(bracketMatch(a,5))
        cout<<"正确"<<endl;
    else
        cout<<"错误"<<endl;
}

bool bracketMatch(char c[], int length) {
    LinkStack stack;
    initStack(stack);
    for (int i = 0; i < length; ++i) {
        char ch = c[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            push(stack, ch);
        } else {
            if (isEmpty(stack))
                return false;
            char cp;
            pop(stack, cp);
            if (ch == ')' && cp != '(')
                return false;
            if (ch == ']' && cp != '[')
                return false;
            if (ch == '}' && cp != '{')
                return false;
        }
    }
    return isEmpty(stack);
}


//初始化
bool initStack(LinkStack &l) {
    l = (LinkNode *) malloc(sizeof(LinkNode));
    l->next = NULL;
    return true;

}

//判空栈
bool isEmpty(LinkStack l) {
    return l->next == NULL;
}

//进栈
bool push(LinkStack &l, char e) {
    LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));
    node->data = e;
    node->next = l->next;
    l->next = node;
    return true;
}

//出栈
bool pop(LinkStack &l, char &e) {
    if (l->next == NULL)
        return false;
    LinkNode *node = l->next;
    l->next = node->next;
    e = node->data;
    free(node);
    return true;
}

//读取栈顶元素
bool getTop(LinkStack &l, char &e) {
    if (l->next == NULL)
        return false;
    e = l->next->data;
    return true;
}

void show(LinkStack l) {
    while (l->next != NULL) {
        l = l->next;
        cout << l->data << "    ";
    }
    cout << endl;
}
